package J4_11;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class test {

    //给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
    //
    //返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Integer[] index = new Integer[n];
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        Arrays.sort(index, (a,b) -> nums2[a] - nums2[b]);
        int left = 0,right = n-1;
        Arrays.sort(nums1);
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            if (nums1[i] > nums2[index[left]]) {
                ret[index[left++]] = nums1[i];
            } else {
                ret[index[right--]] = nums1[i];
            }
        }
        return ret;
    }

    //给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
    //
    //判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;
        for (int i = 0;i < n;i++) {
            if (nums[i] == 0)return false;
            int tmp = 0, cur = 0;
            for(int j = 1; j <=nums[i];j++) {
                if (i + j >= n - 1)return true;
                if (nums[i+j] + j > tmp){
                    tmp = nums[i+j] + j;
                    cur = j;
                }
            }
            i += cur;
        }
        return false;
    }

    //在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
    //
    //你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
    //
    //给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        Queue<Integer> begin = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (gas[i] >= cost[i]) {
                begin.add(i);
            }
        }
        while (!begin.isEmpty()) {
            int cur = begin.poll();
            int tmp = cur;
            int sum = gas[cur];
            int size = gas.length;
            while (size-- >= 1) {
                sum = sum - cost[cur];
                if (sum < 0) break;
                sum = sum + gas[cur];
                cur = (cur+1)%len;
            }
            if (size == -1) {
                return cur;
            }
        }
        return -1;
    }


    //当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
    //
    //给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
    public int monotoneIncreasingDigits(int n) {
        String str = "" + n;
        char[] ch = str.toCharArray();
        for (int i = 0; i < ch.length - 1; i++) {
            if (ch[i] <= ch[i+1]) continue;
            while (i-1 >=0 && ch[i-1] == ch[i]) i--;
            ch[i] = (char)(ch[i]-1);
            for (int j = i+1; j < ch.length; j++) {
                ch[j] = '9';
            }
            break;
        }
        return Integer.parseInt(new String(ch));
    }
}
